There is a service that allows a client (user) to entrust data to an external third party. In a database server used in such a service, data entrusted by a client are stored in a database on the server. In this case, in order to prevent leakage, theft, or the like of information in the database storing the data, from the server side, the data need to be concealed. Information leakage is likely to occur especially in processing of extracting data that satisfy a certain property (for example, data having an attribute that has a certain value), from the server. In order to prevent this, it is desirable not to provide authorization other than a valid client to access the database that stores the data. However, in some situations, an administrator of the server needs permission to access the database for the purpose of managing the data. To address this, a technique has been developed that allows a user to extract desired data in such a server or a system including such a server while keeping the data concealed.
One approach to extracting data from a server in the system as described above while keeping secret of data is a method that uses Searchable Encryption (SE). The method using SE is encryption that allows a text including a search word to be searched for while a plaintext being searched for and a keyword (search word) included in the plaintext are kept encrypted. An encrypted plaintext being searched for is referred to as a ciphertext. In the method using SE, a search token including a search word and a secret key used for encryption is generated when a database is queried. Further, an encryption key included in the generated search token is used to decrypt the ciphertext to check whether the search word is present in a plaintext resulting from the decryption. The processing of the SE method is fast. However, in the SE method, a terminal of a client needs to hold (store) and manage a secret key in order to generate a search token used by the client to query the system.
On the other hand, there is a technique called secret computation using secret sharing scheme, as a method of extracting data without using a secret key. The secret sharing scheme will be described first. The secret sharing scheme is a method in which original secret information can be recovered by converting certain secret information (such as a secret key) to a plurality of pieces of distribution information and collecting a combination of pieces of distribution information that satisfies a certain condition. In this case, it is ensured that information about the original secret information does not leak out when a combination of pieces of distribution information that does not satisfy the certain condition is collected. A typical scheme of the secret sharing scheme is a method that uses Shamir's Secret Sharing (SSS) described in NPL 1. Shamir's Secret Sharing is secret sharing scheme that allows secret information to be recovered by collecting a certain number or more of pieces of distribution information.
Secret computation will be described next. The secret computation is a technique in which a value of any function that takes input of secret information can be calculated by cooperative computation by two or more server devices each of which holds secret information, without leaking respective pieces of secret information. Secret computation methods that use the secret sharing scheme include methods described in NPL 2 and NPL 3.
By distributively holding data being secret information among a plurality of server devises using secret sharing scheme (hereinafter referred to as secret sharing), entrusted data can be concealed from a system administrator being a third party and consequently the entrusted data can be protected from theft. The secret sharing scheme has an advantage that data can be extracted by using secret computation to calculate a function for determining whether or not a specified condition is satisfied, and a client terminal that performs a query does not need to hold a key in the data extraction. However, on the other hand, the secret sharing scheme has a problem that calculation processing of the secret computation takes time.
As a method of extracting data by using SE without using a secret key, a method to calculate a search token in SE by using a secret computation technique may be considered. In this method, a secret key of SE is secret-shared and held by each server along with secret information in a database. To request a search, an inquirer first sends secret-shared data of a search condition that is secret-shared, to each of the servers. Each server uses the secret-shared data of the search condition and secret-shared data of the secret key of SE to perform secret computation, thereby generating a search token.
In this method, data can be extracted without need for the inquirer to have a secret key. However, to decrypt the extracted data, each server needs to use the secret-shared data of the secret key to perform secret computation, and therefore there is also a problem of taking time to obtain a result of data extraction.